package a14_Sort;

import java.util.concurrent.ThreadLocalRandom;

/**
 * @Author quan
 * @Description 快速排序:递归方式
 * @Date 2023/4/28 15:24
 */
public class Demo2_QuickSort {
    public static void main(String[] args) {
        int[] arr = {1,56,23,4,12,9,6,8,17};
        quickSort(arr,0,8);
//        for (int i = 0; i < arr.length; i++) {
//            System.out.println(arr[i]);
//        }
    }
    public static void quickSort(int[] arr,int l, int r){
        //base case
         if(l >= r){
            return;
         }
        /**
         * 优化1：小数组直接使用插入排序
         */
//        if(r-l <= 64){
//            insetSort(arr);
//            return;
//        }
        //定义分区点
        int p = partitionByHole(arr,l,r);
        //让分区点左右的子数组不断快速排序
        quickSort(arr,l,p-1);
        quickSort(arr,p+1,r);
    }

    public static int partitionByHole(int[] arr, int l, int r) {
        /**
         * 优化：每次取分区点的时候，取随机数。->选择一个随机位置与arr[l]交换
         */
        int randomIndex = ThreadLocalRandom.current().nextInt(l,r);
        System.out.print(randomIndex + " ------");
        System.out.println("---------------");
        swap(arr,randomIndex,l);

        //分区点为最左侧元素
        int pivot = arr[l];
        int i = l, j = r;
        while (i < j){
            //让j从右开始一直找到第一个小于pivot的值
            while (i < j && arr[j] > pivot){
                j--;
            }
            //此时j所指的元素是第一个小于pivot的值，将值赋值给i索引上的值
            arr[i] = arr[j];
            //此时从i开始向右找第一个大于pivot的值，放在j索引位置上
            while (i < j && arr[i] < pivot){
                i++;
            }
            //i找到了第一个大于pivot的值
            arr[j] = arr[i];
        }
        //此时i与j指向相同位置，回填分区点
        arr[j] = pivot;
        return j;
    }


    //插入排序
    public static void insetSort(int[] arr){
        //有序区间[0,i)
        //无序区间[i,n)
        for (int i = 1; i < arr.length; i++) {
            //i当前无序区间的第一个值，j表示有序区间新增的值，然后每次新增一个值就要往前看不断调整有序区间使之有序。
            for (int j = i; j >= 1; j--) {
                if(arr[j] < arr[j-1]){
                    swap(arr,j,j-1);
                }
            }
        }
    }

    //交换函数
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
